#include <iostream>

namespace me
{
    template <typename T>
    struct ListNode
    {
        T _val;
        struct ListNode* _next;
        struct ListNode* _prev;

        ListNode(const T& val = T()) 
            :_val(val), _next(nullptr), _prev(nullptr)
        {}
    };

    template <typename T, typename Ref, typename Ptr>
    struct list_iterator
    {
        using node = struct ListNode<T>;
        using self = list_iterator<T, Ref, Ptr>;   
        node* _node;

        list_iterator(node* node)
            :_node(node)
        {}

        Ref operator*() { return _node->_val; }
        Ptr operator->() { return &(_node->_val); }

        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        self operator++(int)
        {
            self tmp(this->_node);
            _node = _node->_next;
            return tmp;
        }

        self operator--(int) 
        {
            self tmp(this->_node);
            _node = _node->_prev;
            return tmp;
        }

        bool operator==(const self& iter) const { return _node == iter._node; }
        bool operator!=(const self& iter) const { return _node != iter._node; }
    };

    template <typename T>
    class list
    {
        using node = struct ListNode<T>;
        using iterator = list_iterator<T, T&, T*>;
        using const_iterator = list_iterator<T, const T&, const T*>;
    public:
        // 默认构造，创建哨兵位头节点
        list()
            :_size(0)
        {
            _head = new node;
            _head->_next = _head;
            _head->_prev  = _head;
        }

        // 带参构造，创建n个val
        list(int n, const T& val = T())
            :_size(0)
        {
            _head = new node();
            _head->_next = _head;
            _head->_prev  = _head;

            for(int i=0; i<n; i++) {
                push_back(val);
            }
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        // 拷贝构造
        list(list& other)
            :_size(0)
        {
            _head = new node();
            _head->_next = _head;
            _head->_prev  = _head;

            const_iterator cbg = other.cbegin();
            while(cbg != other.cend()) {
                push_back(*cbg);
                cbg++;
            }
        }

        list& operator=(list other)
        {
            swap(other);
            return *this;
        }

        void push_back(const T& val)
        {
            // head  tail  newnode  
            // 1.创建新节点
            node* newnode = new node(val);
            node* tail = _head->_prev;
         
            // 2.将newnode链入链表中  
            newnode->_next = _head;
            newnode->_prev = tail;

            // 3.修改原链表指针
            tail->_next = newnode;
            _head->_prev = newnode;
            ++_size;
        }

        // 插入到指定位置之前, pos位置迭代器不失效，返回新插入位置的迭代器
        iterator insert(iterator pos, const T& val)    
        {
            // 1.创建新节点，记录pos位置的节点
            node *newnode = new node(val);
            node* cur = pos._node;

            // prev newnode cur
            // 2.修改指针指向
            newnode->_next = cur;
            newnode->_prev = cur->_prev;
            cur->_prev->_next = newnode;
            cur->_prev = newnode;
            ++_size;

            return iterator(newnode);
        }

        // 删除指定位置的节点，并返回之后位置的迭代器，pos迭代器失效
        iterator erase(iterator pos)
        {
            if(pos == end()) return pos;

            node* cur = pos._node;
            node* prev = cur->_prev;
            node* next = cur->_next;

            // prev cur next
            prev->_next = next;
            next->_prev = prev;
            --_size;

            delete cur;
            return iterator(next);
        }

        // 迭代器相关接口
        iterator begin() { return iterator(_head->_next); }
        const_iterator begin() const { return iterator(_head->_next); }
        const_iterator cbegin() const { return const_iterator(_head->_next); }

        iterator end() { return iterator(_head); } // 指向最后一个元素的下一个位置
        const_iterator end() const { return iterator(_head); }
        const_iterator cend() const { return const_iterator(_head); }

        size_t size() const { return _size; }

        void clear()
        {
            iterator cur = begin();
            while(cur != end()) {
                cur = erase(cur);
            }
            _size = 0;
        }
        
        void swap(list& other)
        {
            std::swap(_head, other._head);
            std::swap(_size, other._size);
        }

        bool empty() const { return _size == 0; }
        T& front() { return _head->_next->_val; }
        const T& front() const { return _head->_next->_val; }
        T& back() { return _head->_prev->_val; }
        const T& back() const { return _head->_prev->_val; }


    private:
        node* _head;
        size_t _size;
    };
}

int main()
{
    me::list<int> il;

    return 0;
}